import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/7 14:35
 * @description 思路，先排序，顺序枚举a , b, 那么  c < a + b
 */
public class Solution {

    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n-2; i++) {
            int a = nums[i];
            for (int j = i + 1; j < n - 1; j++) {
                int b = nums[j];
                int left = j + 1, right = n - 1, k = j;
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (nums[mid] < a + b) {
                        k = mid;
                        left = mid + 1;
                    }else {
                        right = mid - 1;
                    }
                }
                ans += k - j;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Set<Triangle> set = new HashSet<>();
        set.add(new Triangle(1,3,3));
        set.add(new Triangle(1,3,3));
        set.add(new Triangle(2,3,3));
        System.out.println(set.size());
    }

    /**
     * 如果加入的三角形不能包含相同的，那么可以采用Set来去重，Set内存储Triangle结构体，注意重写hashCode 和 equals方法判断重复
     */
    static class  Triangle{
        Integer a;
        Integer b;
        Integer c;
        public Triangle(int a,int b,int c){
            this.a = a;
            this.b = b;
            this.c = c;
        }
        @Override
        public int hashCode() {
            return a.hashCode() * b.hashCode() * c.hashCode();
        }
        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (this == obj) {
                return true;
            }
            if(obj instanceof Triangle){
                Triangle vo = (Triangle) obj;
                if(vo.a.equals(this.a)&&vo.b.equals(this.b)&&vo.c.equals(this.c)){
                    return true;
                }
            }
            return false;
        }
    }
}
